Witsenhausen's counterexample

Contents

A deceptively simple problem

Witsenhausen's counterexample, shown in the figure above, is a deceptively simple toy problem in decentralized stochastic control. It was formulated by Hans Witsenhausen in 1968,[1] and remains unsolved.[2] The importance of the problem was recently reflected upon in the 47th IEEE Conference on Decision and Control (CDC) 2008, Cancun, Mexico, where an entire session was dedicated to understanding the counterexample 40 years after it was first formulated.

The statement of the counterexample is simple: two controllers attempt to control the system by attempting to bring the state close to zero in exactly two time steps. There is a cost on the input u_1 of the first controller, and the state x_2 after the input of the second controller. The input u_2 of the second controller is free, but its observations y_2=x_1%2Bz are noisy. The objective is to minimize an average cost function, k^2E[u_1^2]%2BE[x_2^2], where the average is over the randomness in the initial state x_0 and the observation noise z, both of which are distributed independently and in a Gaussian manner.

The significance of the problem

The counterexample lies at the intersection of control theory and information theory. Due to its hardness, the problem has also received attention from the theoretical computer science community.

The problem is of conceptual significance in decentralized control because it shows that it is important for the controllers to communicate[3] with each other implicitly in order to minimize the cost. This suggests that control actions in decentralized control may have a dual role: those of control and communication.

What conjecture is the problem a counterexample to?

The problem is a counterexample to the natural conjecture from centralized linear-quadratic-Gaussian control systems: that affine control laws are optimal. Witsenhausen showed that there exists a nonlinear control law that outperforms all linear laws.

The hardness of the problem

The hardness of the problem is attributed to the fact that information of the second controller depends on the decisions of the first controller.[4] Variations considered by Tamer Basar [5] show that the hardness is also because of the structure of the performance index and the coupling of different decision variables. It has also been shown that problems of the spirit of Witsenhausen's counterexample become simpler if the transmission delay along an external channel that connects the controllers is smaller than the propagation delay in the problem. However, this result requires the channels to be perfect and instantaneous,[6] and hence is of limited applicability. In practical situations, the channel is always imperfect, and thus one can not assume that decentralized control problems are simple in presence of external channels.

A justification of the failure of attempts that discretize the problem came from the computer science literature: Christos Papadimitriou and John Tsitsiklis showed that the discrete version of the counterexample is NP-complete.[7]

Attempts on obtaining a solution

A number of numerical attempts have been made to solve the counterexample. Focusing on a particular choice of problem parameters (k=0.2,\;\sigma_0=5), researchers have obtained strategies by discretization and using neural networks.[8] Further research (notably, the work of Yu-Chi Ho,[9] and the work of Li, Marden and Shamma [10]) has obtained slightly improved costs for the same parameter choice. The first provably approximately optimal strategies appeared recently (Grover, Park, Sahai) [11] where information theory is used to understand the communication in the counterexample. In the absence of an optimal solution, the problem still remains a puzzle.

References

  1. ^ A counterexample in stochastic optimum control. SIAM J. Control Volume 6, Issue 1, pp. 131–147 (February 1968)
  2. ^ Review of the Witsenhausen problem. Yu-Chi Ho. Proceedings of the 47th IEEE Conference on Decision and Control (CDC), pp. 1611–1613, 2008.
  3. ^ Information and Control: Witsenhausen revisited. Mitter and Sahai. Learning, control and hybrid systems, 1999 – Springer.
  4. ^ Team Decision Theory and Information Structures. Yu-Chi Ho. Proceedings of the IEEE, Vol. 68, No.6, JUNE 1980
  5. ^ Variations on the Theme of the Witsenhausen Counterexample. Tamer Basar. 47th IEEE Conference on Decision and Control Cancun, Mexico, Dec. 9–11, 2008.
  6. ^ Rotkowitz, M.; Cogill, R.; Lall, S.; , "A Simple Condition for the Convexity of Optimal Control over Networks with Delays," Decision and Control, 2005 and 2005 European Control Conference. CDC-ECC '05. 44th IEEE Conference on , vol., no., pp. 6686–6691, 12–15 December 2005
  7. ^ Intractable problems in control theory. Christos Papadimitriou and John Tsitsiklis. 24th IEEE Conference on Decision and Control, 1985
  8. ^ Numerical solutions to the Witsenhausen counterexample by approximating networks. Baglietto, Parisini, Zoppoli IEEE Trans. Automatic Control. 2001.
  9. ^ The Witsenhausen counterexample: A hierarchical search approach for nonconvex optimization problems. Lee, Lau, Ho. IEEE Trans. Automatic Control, 2001
  10. ^ Learning approaches to the Witsenhausen counterexample from a view of potential games. Li, Marden, Shamma. IEEE Conference on Decision and Control, 2009
  11. ^ The finite-dimensional Witsenhausen Counterexample. Grover, Sahai and Park. IEEE WiOpt 2010, ConCom workshop, Seoul, Korea.